import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 25397
 * Date: 2022-02-20
 * Time: 16:15
 */
//刷题：去重考虑Set，考虑次数Map


//力扣138
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
class Solution {
    public Node copyRandomList(Node head) {
        Map<Node,Node> map=new HashMap<>();
        Node tmp=head;
        while(tmp!=null){
            Node newNode=new Node(tmp.val);
            map.put(tmp,newNode);
            tmp=tmp.next;
        }
        tmp=head;
        while(tmp!=null){
            map.get(tmp).next=map.get(tmp.next);
            map.get(tmp).random=map.get(tmp.random);
            tmp=tmp.next;
        }
        return map.get(head);
    }

}


//力扣771
class Solution2 {
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set=new HashSet<>();
        int count=0;
        for(Character c:jewels.toCharArray()){
            set.add(c);
        }
        for(Character c:stones.toCharArray()){
            if(set.contains(c)){
                count++;
            }
        }
        return count;
    }
}

//牛客网-旧键盘打字
class Solution3{
    public static void func(String strExpect, String strActual) {
        Set<Character> set = new HashSet<>();
        //遍历时要把两个字符串都转换成大写，输出只要大写
        for(Character c:strActual.toUpperCase().toCharArray()){//set里面存放实际输出的
            set.add(c);
        }
        Set<Character> broken=new HashSet<>();

        for(Character c2:strExpect.toUpperCase().toCharArray()){
            if(!set.contains(c2)&&!broken.contains(c2)){
                //不包含c2说明实际没有输出c2这个键(c2是坏键)
                System.out.println(c2);
                broken.add(c2);
            }
        }

    }
    public static void main(String[] args) {
        func("7_This_is_a_test","_hs_s_a_es");
    }
}



//力扣692
class Solution4{
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String,Integer>map=new HashMap<>();
        //1.统计每个单词出现的次数
        for (String s:words) {
            if(map.get(s)==null){
                map.put(s,1);
            }else{
                int val=map.get(s);
                map.put(s,val+1);
            }
        }

        //2.建立一个大小为k的小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue())==0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue()-o2.getValue();
            }
        });



        //3.遍历Map
        for (Map.Entry<String,Integer> entry:map.entrySet()) {
            if(minHeap.size()<k){
                minHeap.offer(entry);
            }else{
                //堆中已经放满了k个元素，需要看堆顶元素的数据，和当前数据的大小关系
                Map.Entry<String,Integer> top=minHeap.peek();
                //判断频率是否相同，如果相同，比较单词的大小，单词小的入堆
                if(top.getValue().compareTo(entry.getValue())==0){
                    if(top.getKey().compareTo(entry.getKey())>0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else{
                    if(top.getValue().compareTo(entry.getValue())<0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        System.out.println(minHeap);
        List<String> ret=new ArrayList<>();
        for (int i=0;i<k;i++) {
            Map.Entry<String,Integer> top=minHeap.poll();
            ret.add(top.getKey());
        }
        Collections.reverse(ret);
        return ret;
    }
}
public class test {

}
